package com.base.dp;

import java.util.*;

/**
 * 给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
 *
 * 回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。
 */
public class LongestArithSeqLength {
    public static void main(String[] args) {
        LongestArithSeqLength length = new LongestArithSeqLength();
        System.out.println(length.longestArithSeqLength(new int[]{12,28,13,6,34,36,53,24,29,2,23,0,22,25,53,34,23,50,35,43,53,11,48,56,44,53,31,6,31,57,46,6,17,42,48,28,5,24,0,14,43,12,21,6,30,37,16,56,19,45,51,10,22,38,39,23,8,29,60,18}));
    }



    public int lo(int[] nums){
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        Map<Integer, Integer>[] dp = new HashMap[n];
        //其中 dp[i] 存储了以 nums[i] 结尾的所有可能的公差及其对应的等差子序列长度
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
        }
        int maxLength = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                //看当前i能否加入到当前j的某个公差中，这里的所有公差都会存起来
                int diff = nums[i] - nums[j];
                //当前以j结尾的所有公差中，
                int length = dp[j].getOrDefault(diff, 1) + 1;
                //i从0开始，会存下所有的j
                dp[i].put(diff, length);

                maxLength = Math.max(maxLength, length);
            }
        }
        return maxLength;
    }

    public int longestSubsequence2(int[] arr, int difference,int maxv) {
        int maxLength = 0;
        int[] dp = new int[maxv + 1]; // 这里直接使用 maxv + 1 即可

        for (int num : arr) {
            // 查找 num - difference 是否在 dp 中
            int prevLength = (num - difference >= 0 && num - difference <= maxv) ? dp[num - difference] : 0;
            // 更新 dp[num]

            dp[num] = prevLength + 1;
            // 更新 maxLength
            maxLength = Math.max(maxLength, dp[num]);
        }

        return maxLength;
    }
    public int longestArithSeqLength(int[] nums) {
        int max = Arrays.stream(nums).max().getAsInt();
        int min = Arrays.stream(nums).min().getAsInt();
        int diff = max - min;
        int maxlen = 1;
        for (int i = -diff; i < diff; i++) {
            int i1 = longestSubsequence2(nums, i,max);
            maxlen = Math.max(maxlen,i1);
        }
        return maxlen;
    }
}
